Tech Arsenal 1/Tech Arsenal (Arsenal Computer).ISO/tek-04/ms_sh21s.zip/SH210/SRC/SH12.C

C/C++ Source or Header | 1992-12-14 | 5KB | 215 lines

/* MS-DOS SHELL - TSEARCH functions
 *
 * MS-DOS SHELL - Copyright (c) 1990,1,2 Data Logic Limited and Charles Forsyth
 *
 * This code is based on (in part) the shell program written by Charles
 * Forsyth and is subject to the following copyright restrictions.  The
 * code for the extended (non BASIC) tsearch.3 functions is based on code
 * written by Peter Valkenburg & Michiel Huisjes.  The following copyright
 * conditions apply:
 *
 * 1.  Redistribution and use in source and binary forms are permitted
 *     provided that the above copyright notice is duplicated in the
 *     source form and the copyright notice in file sh6.c is displayed
 *     on entry to the program.
 *
 * 2.  The sources (or parts thereof) or objects generated from the sources
 *     (or parts of sources) cannot be sold under any circumstances.
 *
 *    $Header: /usr/users/istewart/src/shell/sh2.1/RCS/sh12_basic.c,v 1.1 1992/12/14 10:54:56 istewart Exp $
 *
 *    $Log: sh12_basic.c,v $
 * Revision 1.1  1992/12/14  10:54:56  istewart
 * BETA 215 Fixes and 2.1 Release
 *
 */

#include <sys/types.h>
#include <stdio.h>
#include <string.h>
#include <setjmp.h>
#include <unistd.h>
#ifdef OS2
#define INCL_DOSSESMGR
#include <os2.h>            /* DOS functions declarations       */
#else
#include <dos.h>            /* DOS functions declarations       */
#endif
#include "sh.h"

/*
 * Type for doubly linked AVL tree.
 */

/*
 * Definition for t.... functions
 */

typedef struct _t_node {
    char        *key;
    struct _t_node    *llink;
    struct _t_node    *rlink;
} _t_NODE;

static void        _twalk (_t_NODE *,
                void (*)(const void *, VISIT, int), int);
/*
 * Basic Tree Processing Functions
 */

/*
 * Delete node with key
 */

void    *tdelete (key, rootcp, compar)
void    *key;
void    **rootcp;
int    (*compar)(const void *, const void *);
{
    _t_NODE        *p;        /* Parent of node to be deleted */
    register _t_NODE    *q;        /* Successor node        */
    register _t_NODE    *r;        /* Right son node        */
    int            ans;        /* Result of comparison        */
    register _t_NODE    **rootp = (_t_NODE **)rootcp;

    if ((rootp == (_t_NODE **)NULL) || ((p = *rootp) == (_t_NODE *)NULL))
    return (void *)NULL;

    while ((ans = (*compar)(key, (*rootp)->key)) != 0)
    {
    p = *rootp;
    rootp = (ans < 0) ? &(*rootp)->llink : &(*rootp)->rlink;

    if (*rootp == (_t_NODE *)NULL)
        return (void *)NULL;
    }

    r = (*rootp)->rlink;

    if ((q = (*rootp)->llink) == (_t_NODE *)NULL)
        q = r;

    else if (r != (_t_NODE *)NULL)
    {
    if (r->llink == (_t_NODE *)NULL)
    {
        r->llink = q;
        q = r;
    }

    else
    {
        for (q = r->llink; q->llink != (_t_NODE *)NULL; q = r->llink)
        r = q;

        r->llink = q->rlink;
        q->llink = (*rootp)->llink;
        q->rlink = (*rootp)->rlink;
    }
    }

    ReleaseMemoryCell ((char *) *rootp);
    *rootp = q;
    return (void *)p;
}

/*
 * Find node with key
 */

void    *tfind (key, rootcp, compar)
void    *key;            /* Key to be located            */
void    **rootcp;        /* Address of the root of the tree    */
int    (*compar)(const void *, const void *);
{
    register _t_NODE    **rootp = (_t_NODE **)rootcp;

    if (rootp == (_t_NODE **)NULL)
    return (void *)NULL;

    while (*rootp != (_t_NODE *)NULL)
    {
    int    r = (*compar)(key, (*rootp)->key);

    if (r == 0)
        return (void *)*rootp;

    rootp = (r < 0) ? &(*rootp)->llink : &(*rootp)->rlink;
    }

    return (void *)NULL;
}

/*
 * Search for a node with key key and add it if appropriate
 */

void    *tsearch (key, rootcp, compar)
void    *key;            /* Key to be located            */
void    **rootcp;        /* Address of the root of the tree    */
int    (*compar)(const void *, const void *);
{
    register _t_NODE    **rootp = (_t_NODE **)rootcp;
    register _t_NODE    *q;    /* New node if key not found */

    if (rootp == (_t_NODE **)NULL)
    return (void *)NULL;

    while (*rootp != (_t_NODE *)NULL)
    {
    int    r = (*compar)(key, (*rootp)->key);

    if (r == 0)
        return (void *)*rootp;

    rootp = (r < 0) ? &(*rootp)->llink : &(*rootp)->rlink;
    }

    q = (_t_NODE *) GetAllocatedSpace (sizeof (_t_NODE));

    if (q != (_t_NODE *)NULL)
    {
        SetMemoryAreaNumber ((void *)q, 0);
    *rootp = q;
    q->key = key;
    q->llink = q->rlink = (_t_NODE *)NULL;
    }

    return (void *)q;
}


/* Walk the nodes of a tree */

void    twalk (root, action)
void    *root;            /* Root of the tree to be walked */
void    (*action)(const void *, VISIT, int);
{
    if ((root != (char *)NULL) && (action != NULL))
    _twalk (root, action, 0);
}

static void        _twalk (root, action, level)
register _t_NODE    *root;
register void        (*action)(const void *, VISIT, int);
register int        level;
{
    if (root->llink == (_t_NODE *)NULL && root->rlink == NULL)
    (*action)(root, leaf, level);

    else
    {
    (*action)(root, preorder, level);

    if (root->llink != (_t_NODE *)NULL)
        _twalk (root->llink, action, level + 1);

    (*action)(root, postorder, level);

    if (root->rlink != (_t_NODE *)NULL)
        _twalk (root->rlink, action, level + 1);

    (*action)(root, endorder, level);
    }
}